# 扩展欧几里得算法

# 求解ax+by=gcd（a,b）的一组解
# 返回g,x,y
def exgcd(a,b):
    # 递归出口，当b=0时，x=1，y=0
    if b==0:
        return a,1,0
    g,x2,y2=exgcd(b,a%b)
    x1,y1=y2,x2-(a//b)*y2
    return g,x1,y1

# 求解ax+by=m
def Func(a,b,m):
    g,x1,y1=exgcd(a,b)
    # m必须是gcd(a,b)的倍数才有解
    if m%g!=0:
        # 无解
        return None,None,None
    # 方程的一组特解
    x0,y0=x1*m//g,y1*m//g
    return g,x0,y0

# 求a在模n意义下的逆元x，即ax=1 mod n  相等于 ax=ny+1  mod n 的条件下成立
# 即ax+ny=1
def Inv(a,n):
    g,x,y=Func(a,n,1)
    if x is None:
        return None
    else:
        return (x%n+n)%n  # 保证x是 0-n-1 里面的一个数
